import collections
from typing import List


class Solution:
    def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
        block = collections.defaultdict(lambda: collections.defaultdict(list))
        '''
        学到了 defaultdict的设计是工厂模式 需要的参数是一个返回你需要默认值的函数
        比如 list() 返回的是一个列表[]
        所以如果如果要嵌套defaultdict那就需要一个函数返回defaultdict
        '''

        for left, right, top in allowed:
            block[left][right].append(top)

        bottom = list(bottom)

        def DFS(bottom, index) -> bool:
            print("bottom:", bottom, "  index:", index, "  done:", bottom[:index], "   not:", bottom[index:])
            # DFS的节点是每个可能性的分叉，要把整个过程拆出来
            # i就是代表目前进行到 当前序列的哪个部位
            if len(bottom) == 1:
                return True
            elif len(bottom) != 1 and (len(bottom) - 1) == index:
                # 每轮转化结束后进行的处理
                print('deal:')
                if DFS(bottom[:-1], 0):
                    return True
                return False

            tmp = bottom[:index]
            for i in range(index, len(bottom) - 1):
                left, right = bottom[i], bottom[i + 1]
                if right in block[left]:
                    # if len(block[left][right])==1:
                    #     top = block[left][right]
                    #     tmp.append(top)
                    # else:
                    # 就不应该考虑这个优化 破坏代码的完整性和可读性

                    # 注意此处的切分和拼接  A B C D 其中ABC变化出EF 最后一个字母应该由CD拼出
                    for top in block[left][right]:
                        print("left:", left, "  right:", right, "  top:", top)
                        tmp.append(top)
                        # tmp是指已经完成转化的部分
                        if DFS(tmp + bottom[i + 1:], len(tmp)):
                            return True
                        tmp.pop()
                    return False
                else:
                    return False

            return False

        return DFS(bottom, 0)


bottom = "CCC"
allowed = ["CBB", "ACB", "ABD", "CDB", "BDC", "CBC", "DBA", "DBB", "CAB", "BCB", "BCC", "BAA", "CCD", "BDD", "DDD",
           "CCA", "CAA", "CCC", "CCB"]
print(Solution().pyramidTransition(bottom, allowed))
